#lang sicp
(define (make-leaf symbol weight) (list 'leaf symbol weight))
(define (leaf? object) (eq? (car object) 'leaf))
(define (symbol-leaf x) (cadr x))
(define (weight-leaf x) (caddr x))

(define (make-code-tree left right)
  (list left
        right
        (append (symbols left) (symbols right))
        (+ (weight left) (weight right))))

(define (symbols x)
  (if (leaf? x)
      (list (symbol-leaf x))
      (caddr x)))
(define (weight x)
  (if (leaf? x)
      (weight-leaf x)
      (cadddr x)))
(define (left-branch t) (car t))
(define (right-branch t) (cadr t))


(define (decode codes tree)
  (define (helper codes cur-tree)
    (if (null? codes)
        nil
        (let ((next-branch (choose-branch (car codes) cur-tree)))
          (if (leaf? next-branch)
              (cons (symbol-leaf next-branch)
                    (helper (cdr codes) tree))
              (helper (cdr codes) next-branch)))))
  (helper codes tree))
(define (choose-branch bit tree)
    (cond ((= 1 bit) (right-branch tree))
          ((= 0 bit) (left-branch tree))
          (else (error "error -- CHOOSE-BRANCH" bit))))

(define (ordered-leaves-sets-to-code-tree sets)
  (define (reduce sets)
    (if (null? (cdr sets))
        (car sets)
        (let ((min1 (car sets))
              (min2 (cadr sets))
              (rest (cddr sets)))
          (ordered-leaves-sets-to-code-tree (adjoin-set (make-code-tree min1 min2)
                                                        rest)))))
  (reduce sets))
(define (unordered-to-ordered-leaves-sets sets)
  (if (null? sets)
      nil
      (adjoin-set (cons 'leaf (car sets))
                  (unordered-to-ordered-leaves-sets (cdr sets)))))
(define (adjoin-set x sets)
  (cond ((null? sets) (list x))
        (else (let ((x-w (weight x))
                    (cur-w (weight (car sets))))
                (cond ((> x-w cur-w)
                       (cons (car sets)
                             (adjoin-set x (cdr sets))))
                      (else
                       (cons x sets)))))))


;;2.68
(define (encode msg tree)
  (define (encode-msg msg)
    (if (null? msg)
        nil
        (let ((char (car msg)))
          (if (not (element-of-set? char (symbols tree)))
              (error "the char is not contained the code tree" char)
              (encode-char char (cdr msg) tree)))))
  (define (encode-char char msg cur-tree)
    (cond ((leaf? cur-tree)
           (encode-msg msg))
          (else
           (let ((left (left-branch cur-tree))
                 (right (right-branch cur-tree)))
             (if (element-of-set? char (symbols left))
                 (cons 0
                       (encode-char char msg left))
                 (cons 1
                       (encode-char char msg right)))))))
  (encode-msg msg))

(define (element-of-set? el set)
  (cond ((null? set) #F)
        ((eq? el (car set)) #T)
        (else (element-of-set? el (cdr set)))))


(define (generate-huffman-tree pairs)
  (ordered-leaves-sets-to-code-tree (unordered-to-ordered-leaves-sets pairs)))


;; example
(define tree2 (generate-huffman-tree '((a 3) (b 2) (c 5) (d 2) (f 1))))
(define sample-tree
  (make-code-tree (make-leaf 'A 4)
                  (make-code-tree
                   (make-leaf 'B 2)
                   (make-code-tree
                    (make-leaf 'D 1)
                    (make-leaf 'C 1)))))
(define sample-message '(0 1 1 0 0 1 0 1 0 1 1 1 0))

;;2.70
(define song-tree
  (generate-huffman-tree
   '((a 2) (get 2) (sha 3) (wah 1) (boom 1) (job 2) (na 16) (yip 9))))
(define song-message
  '(get a job
        sha na na na na na na na na
        get a job
        sha na na na na na na na na
        wah yip yip yip yip yip yip yip yip yip
        sha boom
        ))
(define encoded-song (encode song-message song-tree))
;; only need 3 fixed-length code for each of the eight-symbol alphabet
;; samllest number of bits is 3 * words length of the song, is 3 * 36 equal 108
;; but huffman-encode is only 84 bits



;; Exercise 2.71
;; if frequencies of symbols is 1, 2, 4, 8, ... , 2 ^ n-1
;; for the most frequent symbol, require n-1 bits
;; for the least frequent symbol, require 1 bit


;; Exercise 2.72
;; the number of steps needed to search the symbol list at each node, depend on
;  data structure of symbol list; there is O(n);
;; thus, for the most frequent symbol, O(n) * 2: O(n)
;        for the least frequent symbol, O(n)*n:  O(n*n);